package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月30日
*时间：下午2:37:03
*/
public class Q140 {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        if (b == 1) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }
        a = a % b;
        long c = 1;
        long d = a;
        while (n > 0) {
            if ((n & 1) == 1) {
                c = (c * d) % b;
            }
            n = n >> 1;
            d = (d * d) % b;
        }
        return (int) c;
    }

    @Test
    public void testA() {
        // 2, 2147483647, 2147483647
        // 109, 10000007, 1000001
        // System.out.println(fastPower(2, 2147483647, 2147483647));
        System.out.println(fastPower(109, 10000007, 1000001));
    }
}
